#include <stdio.h>
#include <stdlib.h>

typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;

void Intersection(List La,List Lb);

//创建头指针为la, lb的两个链表
void createlink(List *pla, List *plb)
{
	int i;
	Node *p;

	*pla = (Node *)malloc(sizeof(Node));     //创建头结点
	p = *pla;

	for(i = 1; i <=10;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));		
		p = p->next;
		p->d = i*2;
		p->next = NULL;
	}


	*plb = (Node *)malloc(sizeof(Node));     //创建头结点
	p = *plb;

	for(i = 1; i <= 8;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));		
		p = p->next;
		p->d = i+6;
		p->next = NULL;
	}
}

void main()
{
	int i;

	List la, lb;
	Node *p;

	createlink(&la, &lb);
	Intersection (la, lb);
	
	p = la->next;
	while(p!=NULL)
	{
		printf("%4d",p->d);
		p = p->next;
	}
	printf("\n");
}


//输入两个链表首节点地址
//题目所求函数 功能:合并AB表,严格递增
void Intersection(List La,List Lb){
    

    Node *pre =La;    //pre初始为La,在过程中作为存储器使用,一直存储上一个待定义指针域的节点
    Node *p1=La->next;//p1为La的第一个元素，在程序中用于遍历A链表
    Node *p2=Lb->next;//p2为Lb的第一个元素，在程序中用于遍历B链表

	Node *LaDelete;//改进:用于存储需要删除的节点地址

    //当两链表均未到末尾时
    while (p1!=NULL && p2!=NULL)
    {
        //大小相同，直接同时向后跳转,即为所求的交集
        if(p1->d==p2->d){
            pre->next = p1;
            pre =p1;
            p1=p1->next;
            p2=p2->next;
        }
        //谁小谁想后走动一个
        else if(p1->d>p2->d){
            
            p2=p2->next;
        }else{
            LaDelete=p1;//改进:记录要删除的节点
            p1=p1->next;
			free(LaDelete);//改进:删除
        }
    }
    
    //若已遍历到末尾尚未结束,说明剩下的均为不相等的元素，需要直接删除

    if(p1!=NULL){
        pre->next=NULL;
    }

	//改进:删除A链表剩余的节点空间
	while(p1!=NULL){
		LaDelete=p1;
		p1=p1->next;
		free(LaDelete);
	}
    


}



/*
设计一个函数
	void  Intersection (List La, List Lb)
其功能是求Lb和La的交集，且将交集的结果置于La中，其中La和Lb的元素均为严格递增有序排列，求交集后的La的元素也为严格递增有序排列。La和Lb是带头结点的单向链表。
其中List是如下结构体：
typedef struct T_Node{
	int d;
	struct T_Node *next;
} Node, *List;
函数中，不得生成新的结点，尽量利用已经有的结点。

如下的main函数执行后
//创建头指针为la, lb的两个链表
void createlink(List *pla, List *plb)
{
	int i;
	Node *p;

	*pla = (Node *)malloc(sizeof(Node));     //创建头结点
	p = *pla;

	for(i = 1; i <=10;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));		
		p = p->next;
		p->d = i*2;
		p->next = NULL;
	}


	*plb = (Node *)malloc(sizeof(Node));     //创建头结点
	p = *plb;

	for(i = 1; i <= 8;i++)
	{
		p->next = (Node *)malloc(sizeof(Node));		
		p = p->next;
		p->d = i+6;
		p->next = NULL;
	}
}

void main()
{
	int i;

	List la, lb;
	Node *p;

	createlink(&la, &lb);
	Intersection (la, lb);
	
	p = la->next;
	while(p!=NULL)
	{
		printf("%4d",p->d);
		p = p->next;
	}
	printf("\n");
}
执行的结果为
   8  10  12  14

*/